package zuoshen.chapter1;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class DescStack {


    public static void main(String[] args) {
        int[] arr = new int[]{3,1,3,4,3,5,3,2,2};
//        int[] arr = new int[]{3,4,1,5,6,2,7};
        int[][] nearLess = findNearLessAdv(arr);
        for (int[] less : nearLess) {
            System.out.print(Arrays.toString(less));
        }
    }

    /**
     * 返回数组各元素左右两边最近的较小元素的下标，数组中元素各不相同
     * 按单调栈的出栈方式，被弹出的元素左边最近较小就是栈顶，右边最近较小就是要入栈的
     */
    public static int[][] findNearLess(int[] arr){
        int[][] res = new int[arr.length][2];
        Stack<Integer> descStack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!descStack.isEmpty()&&arr[descStack.peek()]>arr[i]){
                int popNum = descStack.pop();
                res[popNum][0] = descStack.isEmpty()?-1:descStack.peek();
                res[popNum][1] = i;
            }
            descStack.push(i);
        }
        //处理栈中剩余元素，这些元素无法出栈是因为右边没有更小元素
        //左边最近较小元素就是栈中前一个元素
        while (!descStack.isEmpty()){
            int popNum = descStack.pop();
            res[popNum][0] = descStack.isEmpty()?-1:descStack.peek();
            res[popNum][1] = -1;
        }
        return res;
    }

    /**
     * 进阶：arr有重复元素，这会造成出栈的元素左边最近较小的元素不一定是栈顶，因为可能和栈顶相等
     * 做一个类似挂在Hash数组链表的数据结构，相同的元素放在一个容器中，该容器放在单调栈中
     */
    public static int[][] findNearLessAdv(int[] arr){
        int[][] res = new int[arr.length][2];
        Stack<LinkedList<Integer>> descStack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!descStack.isEmpty()&&arr[descStack.peek().peekFirst()]>arr[i]){
                //集合中元素都比arr[i]小
                LinkedList<Integer> popList = descStack.pop();
                for (Integer integer : popList) {
                    res[integer][0] = descStack.isEmpty()?-1:descStack.peek().peekLast(); //这一句可以拿到外边
                    res[integer][1] = i;
                }
            }
            //arr[i]入栈，为保持容器唯一性需要判断arr[i]是否属于栈顶容器
            if(descStack.isEmpty()||arr[descStack.peek().peekFirst()]!=arr[i]){
                LinkedList<Integer> pushList = new LinkedList<>();
                pushList.addLast(i);
                descStack.push(pushList);
            }else{
                descStack.peek().addLast(i);
            }
        }
        //处理栈中剩余元素，这些元素无法出栈是因为右边没有更小元素
        //左边最近较小元素就是栈中前一个元素
        while (!descStack.isEmpty()){
            LinkedList<Integer> popList = descStack.pop();
            for (Integer integer : popList) {
                res[integer][0] = descStack.isEmpty()?-1:descStack.peek().peekLast();
                res[integer][1] = -1;
            }
        }
        return res;
    }
}
